A goal of automatic speech recognition (ASR) is generally to recognize words given some audio signal. ASR may be represented probabilistically as a maximization problem, where a word sequence is chosen to have the highest likelihood given an acoustic sequence. Such maximization problems may involve finite-state transducers, which are generally used in recognition applications, such as speech or handwriting recognition, gesture recognition and so on. For example, finite-state transducers may be used in speech-to-text and text-to-speech systems to represent various aspects of a recognition and/or a conversion process.
Weighted finite-state transducers may be used to provide a common representation for each component of a complex system in many applications. Such weighted finite-state transducers may involve methods for simplifying and/or combining components, such as the composition of two weighted finite-state transducers. A finite-state transducer is deterministic if that finite-state transducer has a unique initial state and if no two transitions of the finite-state transducer leaving the same state have the same input label.